package Hot100;

import java.util.ArrayList;
import java.util.List;

public class 课程表 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjList.add(new ArrayList<>());
        int[] flags = new int[numCourses];
        for (int[] prerequisite : prerequisites) adjList.get(prerequisite[0]).add(prerequisite[1]);
        for (int i = 0; i < numCourses; i++) if (!dfs(adjList, flags, i)) return false;
        return true;
    }

    private boolean dfs(List<List<Integer>> adjList, int[] flags, int i) {
        if (flags[i] == 1) return false;
        if (flags[i] == -1) return true;
        flags[i] = 1;
        for (Integer j : adjList.get(i)) if (!dfs(adjList, flags, j)) return false;
        flags[i] = -1;
        return true;
    }
}
